Partitioning Trillion-edge Graphs in Minutes

摘要

We introduce XtraPuLP, a new distributed-memory graph partitioner designed toprocess trillion-edge graphs. XtraPuLP is based on the scalable labelpropagation community detection technique, which has been demonstrated as aviable means to produce high quality partitions with minimal computation time.On a collection of large sparse graphs, we show that XtraPuLP partitioningquality is comparable to state-of-the-art partitioning methods. We alsodemonstrate that XtraPuLP can produce partitions of real-world graphs withbillion+ vertices in minutes. Further, we show that using XtraPuLP partitionsfor distributed-memory graph analytics leads to significant end-to-endexecution time reduction.